package srm512;

import java.util.Arrays;

public class SubFibonacci {

    private int N;
    private int[] fib;

    public int maxElements(int[] S) {
        N = S.length;
        fib = new int[52];
        fib[0] = 0;
        fib[1] = 1;
        for (int i = 2; i < fib.length; i++) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }

        Arrays.sort(S);
        int max = 0;
        for (int i = 0; i <= N; i++) {
            max = Math.max(max, solve(S, 0, i) + solve(S, i, N));
        }
        return max;
    }

    private int solve(int[] s, int i, int f) {
        if (f - i <= 2) return f - i;
        int result = 2;

        for (int k = i; k < f - 2; k++) {
            for (int l = k + 1; l < f - 1; l++) {
                int a = 0, b;
                boolean valid = false;
                for (int j = 0; j <= 40; j++) {
                    valid = false;
                    if (j == 0) {
                        a = s[k];
                        b = s[l];
                        valid = true;
                    } else {
                        b = s[l];
                        int z = (b - fib[j] * s[k]) / fib[j + 1];
                        if (z > b || z <= 0) break;
                        if (b == (fib[j] * s[k] + fib[j + 1] * z)) {
                            a = fib[j - 1] * s[k] + fib[j] * z;
                            valid = true;
                        } else if (b < (fib[j] * s[k] + fib[j + 1] * z)) {
                            break;
                        }
                    }
                    if (!valid) {
                        continue;
                    }
                    int tot = 2, next = a + b;
                    for (int m = l + 1; m < f; ) {
                        if (s[m] == next) {
                            tot++;
                            a = b;
                            b = next;
                            next = a + b;
                            m++;
                        } else if (s[m] > next) {
                            a = b;
                            b = next;
                            next = a + b;
                        } else {
                            m++;
                        }
                    }
                    if (tot > result)
                        result = tot;
                }
            }
        }
        return result;
    }

    // BEGIN KAWIGIEDIT TESTING
    // Generated by KawigiEdit 2.1.8 (beta) modified by pivanof
    private static boolean KawigiEdit_RunTest(int testNum, int[] p0, boolean hasAnswer, int p1) {
        System.out.print("Test " + testNum + ": [" + "{");
        for (int i = 0; p0.length > i; ++i) {
            if (i > 0) {
                System.out.print(",");
            }
            System.out.print(p0[i]);
        }
        System.out.print("}");
        System.out.println("]");
        SubFibonacci obj;
        int answer;
        obj = new SubFibonacci();
        long startTime = System.currentTimeMillis();
        answer = obj.maxElements(p0);
        long endTime = System.currentTimeMillis();
        boolean res;
        res = true;
        System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
        if (hasAnswer) {
            System.out.println("Desired answer:");
            System.out.println("\t" + p1);
        }
        System.out.println("Your answer:");
        System.out.println("\t" + answer);
        if (hasAnswer) {
            res = answer == p1;
        }
        if (!res) {
            System.out.println("DOESN'T MATCH!!!!");
        } else if ((endTime - startTime) / 1000.0 >= 2) {
            System.out.println("FAIL the timeout");
            res = false;
        } else if (hasAnswer) {
            System.out.println("Match :-)");
        } else {
            System.out.println("OK, but is it right?");
        }
        System.out.println("");
        return res;
    }

    public static void main(String[] args) {
        boolean all_right;
        all_right = true;

        int[] p0;
        int p1;

        // ----- test 0 -----
        p0 = new int[]{8, 1, 20, 3, 10};
        p1 = 5;
        all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;
        // ------------------

        // ----- test 1 -----
        p0 = new int[]{19, 47, 50, 58, 77, 99};
        p1 = 4;
        all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;
        // ------------------

        // ----- test 2 -----
        p0 = new int[]{512};
        p1 = 1;
        all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;
        // ------------------

        // ----- test 3 -----
        p0 = new int[]{3, 5, 7, 10, 13, 15, 20, 90};
        p1 = 7;
        all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;
        // ------------------

        // ----- test 4 -----
        p0 = new int[]{1, 2, 3, 5, 8, 13, 21, 34, 55, 89};
        p1 = 10;
        all_right = KawigiEdit_RunTest(4, p0, true, p1) && all_right;
        // ------------------

        if (all_right) {
            System.out.println("You're a stud (at least on the example cases)!");
        } else {
            System.out.println("Some of the test cases had errors.");
        }
    }
    // END KAWIGIEDIT TESTING
}
//Powered by KawigiEdit 2.1.8 (beta) modified by pivanof!
